//
// Created by lanlu on 2025/8/13.
//

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:

    void printVector(vector<bool> v)
    {
        cout << "bool:";
        for (bool i : v)
        {
            cout << i << " ";
        }
        cout << endl;
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        // 可以标记城市是否被访问
        vector<bool> isvisit(n, false);
        // 省份数量
        int cnt = 0;
        // 从第一个城市开始遍历 第一个一维数组代表第一个城市到其他城市是否可达
        // 遍历完第一个一维数组 此时第一个城市和其他城市所组成的省份可以找到
        // 从第二个城市开始 查看是否已访问 如果未访问 代表找到一个新省份
        for (int i = 0; i < n; i++) {
            cout << "i=" << i << endl;
            // [1,1,0]  [false,false,false]
            if (isvisit[i] == false) {
                // 将第一个城市能够访问的所有城市 设为已访问
                dfs(isConnected, isvisit, i);
                cnt++;
                cout << "cnt=" << cnt << endl;
                printVector(isvisit);
            }
        }
        return cnt;
    }
    void dfs(vector<vector<int>>& isConnected, vector<bool> &isvisit, int city) {
        cout << "dfs: city=" << city << endl;
        // city=0 [true,false,false]
        // city=1 [true,true,false]
        isvisit[city] = true;
        for (int j = 0; j < isConnected.size(); j++) {
            // 如果当前城市和找到的城市相连 且这个城市没有被访问过
            // city = 0 [1,1,0]  [true,false,false]
            // city = 1 [1,1,0]  [true,true,false]
            if (isConnected[city][j] == 1 && isvisit[j] != true) {
                dfs(isConnected, isvisit, j);
            }
        }
    }
};

int main() {
    vector<vector<int>> isConnected = {{1,1,0},{1,1,0},{0,0,1}};
    int circle_num = Solution().findCircleNum(isConnected);
    cout << circle_num << endl;
}


